package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/17 17:10
 * @description: TODO
 */
public class _060_两个字符串删除 {

    @Test
    public void test1() {
        System.out.println(minDistance("sea", "eat"));
    }

    /**
     * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
     * 每步 可以删除任意一个字符串中的一个字符。
     * <p>
     * 可以找到他们的最长公共子序列,然后将两串的长度相加-公共子序列的长度*2,就是需要删除的次数
     */
    private int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int[][] dp = new int[charArray1.length + 1][charArray2.length + 1];
        for (int i = 1; i < charArray1.length + 1; i++) {
            for (int j = 1; j < charArray2.length + 1; j++) {
                if (charArray1[i - 1] == charArray2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
//            System.out.println(Arrays.toString(dp[i]));
        }
        return word1.length() + word2.length() - 2 * dp[charArray1.length][charArray2.length];
    }
}
